/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package open.algo.sort;

/**
 * http://blogs.sun.com/darcy/date/20090727
 * http://www.javabeat.net/articles/print.php?article_id=14
 *
 * @SortAnnoation(averageTime="o(nlogn)", worstTime="o(n2)", space = "o(logn)", stable = true, feature= "good in amortized time")
 * @author fli
 */
public class QuickSort implements Sort
{

    public static int method = 2;

    @Override
    public void sort(int[] a)
    {
        switch (method)
        {
            case 1:
                qsort_1(a, 0, a.length - 1);
                break;
            case 2:
                qsort_2(a, 0, a.length - 1);
                break;
            default:
                qsort(a, 0, a.length - 1);
        }
    }

    private void qsort_2(int[] a, int s, int e)
    {
        //pivot index
        int pi = (s + e) / 2;

        Swap.swap(a, pi, e);

        //store index
        int si = s;
        for (int i = s; i < e; i++)
        {
            if (a[i] <= a[e])
            {
                Swap.swap(a, si, i);
                si++;
            }
        }

        Swap.swap(a, si, e);

        if (s < si - 1)
        {
            qsort_2(a, s, si - 1);
        }
        if (e > si + 1)
        {
            qsort_2(a, si + 1, e);
        }
    }

    private void qsort_1(int[] a, int s, int e)
    {
        //use s as pivot index
        int pivot = a[s];

        int i = s, j = e;
        while (i < j)
        {
            while (i < j && a[j] >= pivot)
            {
                j--;
            }
            a[i] = a[j];
            while (i < j && a[i] <= pivot)
            {
                i++;
            }
            a[j] = a[i];
        }

        // i = j
        a[i] = pivot;

        if (s < i - 1)
        {
            qsort_1(a, s, i - 1);
        }
        if (e > i + 1)
        {
            qsort_1(a, i + 1, e);
        }
    }

    private void qsort(int[] a, int s, int e)
    {
        //  pivotIndex
        int pi = (s + e) / 2;
        int pivot = a[pi];

        int i = s, j = e;
        while (i < j)
        {
            while (i < j && a[j] >= pivot)
            {
                j--;
            }
            a[pi] = a[j];
            pi = j;
            while (i < j && a[i] <= pivot)
            {
                i++;
            }
            a[pi] = a[i];
            pi = i;
        }

        // i = j = pivotIndex
        a[i] = pivot;

        if (s < i - 1)
        {
            qsort(a, s, i - 1);
        }
        if (e > i + 1)
        {
            qsort(a, i + 1, e);
        }
    }

    @Override
    public String toString()
    {
        return "quicksort";
    }
}
